package leetcode.code0828;

import leetcode.helper.HelpDebug;

public class Solution2 extends Solution828 {

	private static final char A = 'A';
	private int M = (int) 1e9 + 7;

	@Override
	public int uniqueLetterString(String s) {
		int len = s.length();
		int ans = 0;
		char[] chars = s.toCharArray();
		int[][] dp = new int[len][len];
		for (int i = 0; i < len; i++) {
			dp[0][i] = 1;
			ans += 1;
		}
		for (int row = 1; row < len; row++) {
			int[] dic = new int[26];
			int l = 0;
			for (int i = l; i < row; i++) {
				dic[chars[i] - A]++;
			}
			for (int col = row; col < len; col++) {
				char c = chars[col];
				int num = 0;
				int cur = c - A;
				if (dic[cur] == 0) {
					num = dp[row - 1][col - 1] + 1;
				} else if (dic[cur] == 1) {
					num = dp[row - 1][col - 1] - 1;
				} else {
					num = dp[row - 1][col - 1];
				}
				dp[row][col] = num;
				ans += num;
				ans = (ans + M) % M;
				dic[chars[l++] - A]--;
				dic[cur]++;
			}
		}
		HelpDebug.print(dp);
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
//		so.debug4();
	}

}
